package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/21 15:09
 **/
public class Day36_5_Num72_MinDistance {
    class Solution {
        public int minDistance(String word1, String word2) {
            int len1 = word1.length(), len2 = word2.length();
            int[][] dp = new int[len1+1][len2+1];
            for(int i = 0; i <= len1; ++i) dp[i][0] = i;
            for(int j = 0; j <= len2; ++j) dp[0][j] = j;

            for(int i = 1; i <= len1; ++i){
                for(int j = 1; j <= len2; ++j){
                    if(word1.charAt(i-1) == word2.charAt(j-1)){
                        dp[i][j] = dp[i-1][j-1];
                    }else{
                        dp[i][j] = 1 + Math.min(Math.min(dp[i][j-1], dp[i-1][j]), dp[i-1][j-1]);
                    }
                }
            }
            return dp[len1][len2];
        }
    }
}